package com.zjsru.plan2024.oneday;

/**
 * 322. 零钱兑换
 * @Author: cookLee
 * @Date: 2024-03-24
 */
public class CoinChange {

    /**
     * 主
     * \
     * 输入：coins = [1, 2, 5], amount = 11
     * 输出：3
     * 解释：11 = 5 + 5 + 1
     * \
     * 输入：coins = [2], amount = 3
     * 输出：-1
     * \
     * 输入：coins = [1], amount = 0
     * 输出：0
     * \
     * @param args args
     */
    public static void main(String[] args) {
        CoinChange coinChange = new CoinChange();
        int[] coins = new int[]{1, 2, 5};
        int amount = 5;
        System.out.println(coinChange.coinChange(coins, amount));
    }

    /**
     * 硬币变化
     *
     * @param coins  硬币
     * @param amount 金额
     * @return int
     */
    public int coinChange(int[] coins, int amount) {
        if (amount < 1) {
            return 0;
        }
        return this.helper(coins, amount, new int[amount]);
    }

    /**
     * 助手类
     *
     * @param coins  硬币
     * @param rem 所需金额
     * @param count   记录凑成金额rem最小的硬币数
     * @return int
     */
    private int helper(int[] coins, int rem, int[] count) {
        if (rem < 0) {
            return -1;
        }
        if (rem == 0) {
            return 0;
        }
        if (count[rem - 1] != 0) {
            return count[rem - 1];
        }
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = this.helper(coins, rem - coin, count);
            if (res >= 0 && res < min) {
                min = res + 1;
            }
        }
        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];
    }
}
